/**
 * 题目: 两数之和
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 两种方法:
 * 1. 暴力枚举 : 先固定一个数, 再循环遍历后面的数, 可以解决, 但时间复杂度较大 O(n^2) 空间复杂度 O(1)
 * 2. 使用一个 Map 将数组的值和下标全都存在 Map中, 然后再遍历一遍数组, 这事只需要在
 * Map中寻找 target - nums[i]存不存在即可,若存在返回 Map中存的下标和此时的数组下标
 * 不用担心后面遇到重复的数怎么存, 直接存就好了, 因为本题只要求返回其中一组下标就好可以了
 * 时间复杂度O(n) 空间复杂度 O(n)
 *
 * 方法二优化 : 可以边在 Map中存数据, 边从 Map中寻找 target - nums[i](利用前缀和思想)
 */

public class Main {
    // 暴力枚举
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 固定一个数
            for (int j = i + 1; j < n; j++) {
                // 第二个数从 i + 1开始, 为什么不从零开始呢, 因为前面的数都已经在前面的遍历中验过了
                if (nums[i] + nums[j] == target) {
                    // 若是找到两个数符合要求, 直接返回两个数的下标
                    return new int[]{i, j};
                }
            }
        }
        return new int[2];
    }

    // 方法二
    public int[] twoSum1(int[] nums, int target)  {
        int n = nums.length;
        // 创建一个 Map记录下数组中出现的数和它的下标
        Map<Integer, Integer> hash = new HashMap<>();
        // 记录数据, 有重复直接覆盖
        for (int i = 0; i < n; i++) hash.put(nums[i], i);
        for (int i = 0; i < n; i++) {
            // 在 Map中寻找符合要求的数据, 并用短路特性要求在找到时此次下标不能与这时的下标相同
            if (hash.containsKey(target - nums[i]) && hash.get(target - nums[i]) != i) {
                return new int[]{hash.get(target - nums[i]), i};
            }
        }
        return new int[2];
    }

    // 优化方法二
    // 一个难点就是在何时找数据, 何时存数据
    // 首先我们在遇到一个数的时候是在之前存的数中找寻符合要求的数的,
    // 那在找的时候是一定是先找再存的, 因为如果我们先存数据在进行查找数据会导致我们可能找的是自己本身
    public int[] twoSum2(int[] nums, int target) {
        int n = nums.length;
        int[] arr = new int[2];
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < n; i++) {
            // 先寻找寻数据
            if (hash.containsKey(target - nums[i])) {
                arr[0] = hash.get(target - nums[i]);
                arr[1] = i;
                // 在找到时直接break就可以了
                break;
            }
            // 存数据
            hash.put(nums[i], i);
        }
        return arr;
    }
}
